import java.util.Stack;

/*
 * @author zzr
 * @date: 2025/10/18  20:10
 * @description: 非递归方法先序遍历二叉树
 *
 */
public class Demo33 {


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public void preOrderNor(TreeNode root) {
        // 处理空树的情况
        if (root == null) return;

        // 借助一个栈进行遍历
        // 前序遍历
        // 站里面存放的是已经访问过的根节点，但尚未处理这个节点的
        // 右子树的节点
        Stack<TreeNode> stack = new Stack<>();

        // cur 是一个用于指向当前正在处理的节点的引用
        TreeNode cur = root;

        // top 用于存储栈弹出的顶端接待你
        TreeNode top = null;

        // cur ！= null 说明当前仍有未访问的左子树节点，
        // 需要将 cur 入栈（后续处理他的右子树）
        // 访问 cur （前序遍历：根左右）
        // 继续遍历 cur 的左子树

        // cur == null 但是 !stack.isEmpty()
        // 此时 cur 为空，说明当前路径的左子树已经遍历完毕
        // 但栈中仍然存在节点
        // 栈中存在的节点是之前保存的，已经访问根节点，但未处理右子树的节点
        // 需要 从栈中弹出栈顶节点（top）
        // 将cur 指向 top 的右子树（开始处理右子树）
        while (cur != null || !stack.isEmpty()) {

            while (cur != null) {
                stack.push(cur);
                System.out.println(cur.val + " ");
                cur = cur.left; // 先序遍历， 根左右 先向左侧
            }
            // 内循环完毕后
            top = stack.pop();
            cur = top.right;
        }
    }
}
